package cn.edu.zufe.mjt.dp;

import java.util.Scanner;

/**
 * 给定一个大小为n * n的二维矩阵，计算从起点(1,1)到终点(n,n)的所有可能路径的数量。每一步可以向右或向下移动一个格子。
 */
public class MatrixPathQuestion {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] matrix = new int[n][n];
        int result = countPaths(matrix);
        System.out.println(result);
    }

    /**
     * 数学推导五步法
     * ① 构造集合:从具体例子出发，列出所有情况
     * ② 寻找等式:根据集合元素中上一个位置的取值进行集合划分
     * ③ 集合映射:去掉集合元素的最后一个元素，集合映射为子问题形式
     * ④ 推广得到递推式
     * ⑤ 列举边界情况
     * <br>
     * 假设 n=3
     * <p>
     * D(2,2)
     * (0,0)->(0,1)->(0,2)->(1,2)->(2,2)
     * (0,0)->(0,1)->(1,1)->(1,2)->(2,2)
     * (0,0)->(0,1)->(1,1)->(2,1)->(2,2)
     * (0,0)->(1,0)->(1,1)->(2,1)->(2,2)
     * (0,0)->(1,0)->(1,1)->(1,2)->(2,2)
     * (0,0)->(1,0)->(2,0)->(2,1)->(2,2)
     * D(1,2)
     * (0,0)->(0,1)->(0,2)->(1,2)
     * (0,0)->(0,1)->(1,1)->(1,2)
     * (0,0)->(1,0)->(1,1)->(1,2)
     * D(2,1)
     * (0,0)->(0,1)->(1,1)->(2,1)
     * (0,0)->(1,0)->(1,1)->(2,1)
     * (0,0)->(1,0)->(2,0)->(2,1)
     * </p>
     * 映射：
     * D(2,2) = D(1,2) + D(2,1)
     * |D(2,2)| = |D(1,2)| + |D(2,1)|，
     * 推广：
     * |D(i,j)| = |D(i-1,j)| + |D(i,j-1)|
     * |D(i,1)| = |D(1,i)| = 1 （边界条件）
     *
     *
     */
    public static int countPaths(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][n - 1];
    }
}
